package com.julius.design.suanfa.linked;

/**
 * @author julius
 * @date 2021-11-03 下午 2:15
 * <p>
 *      找到两个链表的第一个公共点
 *      https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
 * </p>
 */
public class IntersectionNode {

    /**
     * 双指针：
     *
     *      如果有公共节点，则代表
     *
     *      A  长度3   3-2 = 1
     *      B  长度6   6-2 = 4
     *      公共长度 为2
     *      总长度 9
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        //双指针算法
        ListNode pa = headA,pb = headB;
        while (pa != null || pb != null){

            if(pa == pb){
                return pa;
            }

            if(pa == null){
                pa = headB;
            }else{
                pa = pa.next;
            }

            if(pb == null){
                pb = headA;
            }else{
                pb = pb.next;
            }
        }
        return null;
    }


    public class ListNode{
        int val;
        ListNode next;

        ListNode(int x){
            val = x;
            next = null;
        }
    }
}
